// https://leetcode.cn/problems/maximum-product-subarray/

// 题干：给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组
//      （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//      测试用例的答案是一个 32-位 整数。

// 示例：输入: nums = [2,3,-2,4]
//      输出: 6

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int maxProduct(vector<int>& nums)
    {
        // 1.状态表示 f[i]表示以i位置为结尾的所有子数组中最大乘积
        //   状态表示g[i]表示以i位置为结尾的所有子数组中最小乘积
        // 2.状态转移方程
        int n = nums.size();
        vector<int> f(n + 1); f[0] = 1;
        auto g = f;

        int ret = INT_MIN;
        for (int i = 1 ; i <= n ; i++){
            int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1];
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));
            ret = max(ret, f[i]);
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {2,3,-2,4};

    cout << sol.maxProduct(nums) << endl;

    return 0;
}